package com.leetcode.sorts.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: WuPeng
 * @Date: 2021/6/10 3:26 下午
 *
 * 501.二叉搜索树中的众数
 *
 */
public class BinarySearchTree_501 {

    private int maxCount;
    private int count;
    private TreeNode pre = null;
    private List<Integer> answer = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        searchBST(root);
        int[] mode = new int[answer.size()];
        for (int i = 0; i < answer.size(); i++) {
            mode[i] = answer.get(i);
        }
        return mode;
    }

    public void searchBST(TreeNode node){
        if (node == null) return;
        searchBST(node.left);
        updateNode(node);
        searchBST(node.right);
        return;
    }

    private void updateNode(TreeNode node) {
        if (pre == null)
            count = 1;
        else if (pre.val == node.val)
            count++;
        else
            count = 1;

        pre = node;
        if (count == maxCount){
            answer.add(node.val);
        }

        if (count > maxCount){
            maxCount = count;
            answer.clear();
            answer.add(node.val);
        }
    }


}
